// by MoreWindows( http://blog.csdn.net/MoreWindows )
#include <set>
#include <hash_set>
#include <iostream>
#include <ctime>
#include <cstdio>
#include <cstdlib>
using namespace std;
using namespace stdext;  //hash_set

// MAXN个数据 MAXQUERY次查询
const int MAXN = 10000, MAXQUERY = 5000000;
int a[MAXN], query[MAXQUERY];

void PrintfContainertElapseTime(char *pszContainerName, char *pszOperator, long lElapsetime)
{
	printf("%s 的%s操作 用时 %d毫秒\n", pszContainerName, pszOperator, lElapsetime);
}

int main()
{
	printf("set VS hash_set 性能测试 数据容量 %d个 查询次数 %d次\n", MAXN, MAXQUERY);
	const int MAXNUM = MAXN * 4;
	const int MAXQUERYNUM = MAXN * 4;
	printf("容器中数据范围 [0, %d) 查询数据范围[0, %d)\n", MAXNUM, MAXQUERYNUM);
	printf("--by MoreWindows( http://blog.csdn.net/MoreWindows ) --\n\n");
	
	//随机生成在[0, MAXNUM)范围内的MAXN个数
	int i;
	srand(time(NULL));
	for (i = 0; i < MAXN; ++i)
		a[i] = (rand() * rand()) % MAXNUM;
	//随机生成在[0, MAXQUERYNUM)范围内的MAXQUERY个数
	srand(time(NULL));
	for (i = 0; i < MAXQUERY; ++i)
		query[i] = (rand() * rand()) % MAXQUERYNUM;

	set<int>       nset;
	hash_set<int> nhashset;
	clock_t  clockBegin, clockEnd;


	//insert
	printf("-----插入数据-----------\n");

	clockBegin = clock();  
	nset.insert(a, a + MAXN); 
	clockEnd = clock();
	printf("set中有数据%d个\n", nset.size());
	PrintfContainertElapseTime("set", "insert", clockEnd - clockBegin);

	clockBegin = clock();  
	nhashset.insert(a, a + MAXN); 
	clockEnd = clock();
	printf("hash_set中有数据%d个\n", nhashset.size());
	PrintfContainertElapseTime("hase_set", "insert", clockEnd - clockBegin);


	//find
	printf("-----查询数据-----------\n");

	int nFindSucceedCount, nFindFailedCount; 
	nFindSucceedCount = nFindFailedCount = 0;
	clockBegin = clock(); 
	for (i = 0; i < MAXQUERY; ++i)
		if (nset.find(query[i]) != nset.end())
			++nFindSucceedCount;
		else
			++nFindFailedCount;
	clockEnd = clock();
	PrintfContainertElapseTime("set", "find", clockEnd - clockBegin);
	printf("查询成功次数： %d    查询失败次数： %d\n", nFindSucceedCount, nFindFailedCount);
	
	nFindSucceedCount = nFindFailedCount = 0;
	clockBegin = clock();  
	for (i = 0; i < MAXQUERY; ++i)
		if (nhashset.find(query[i]) != nhashset.end())
			++nFindSucceedCount;
		else
			++nFindFailedCount;
	clockEnd = clock();
	PrintfContainertElapseTime("hash_set", "find", clockEnd - clockBegin);
	printf("查询成功次数： %d    查询失败次数： %d\n", nFindSucceedCount, nFindFailedCount);
	return 0;
}
